<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8"/>
<title>constexpr ALL the things!</title>
<meta name="author" content="(Ben Deane & Jason Turner)"/>
<style type="text/css">
.underline { text-decoration: underline; }
</style>
<link rel="stylesheet" href="./reveal.js/css/reveal.css"/>

<link rel="stylesheet" href="./reveal.js/css/theme/blood.css" id="theme"/>

<link rel="stylesheet" href="./presentation.css"/>

<!-- If the query includes 'print-pdf', include the PDF print sheet -->
<script>
    if( window.location.search.match( /print-pdf/gi ) ) {
        var link = document.createElement( 'link' );
        link.rel = 'stylesheet';
        link.type = 'text/css';
        link.href = './reveal.js/css/print/pdf.css';
        document.getElementsByTagName( 'head' )[0].appendChild( link );
    }
</script>
</head>
<body>
<div class="reveal">
<div class="slides">
<section id="sec-title-slide"><img src="title.png"><h3>Ben Deane / <a href="mailto:bdeane@blizzard.com">bdeane@blizzard.com</a> / <a href="http://twitter.com/ben_deane">@ben_deane</a></h3><h3>Jason Turner / <a href="mailto:jason@emptycrate.com">jason@emptycrate.com</a> / <a href="http://twitter.com/lefticus">@lefticus</a></h3><h4>CppCon / Monday 25th September 2017</h4>
</section>
<script type="text/javascript" src="./presentation.js"></script>

<section>
<section id="slide-orga780e29">
<h2 id="orga780e29">The Goal</h2>
<p>
We want to do this:
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsv</span>
  = R<span style="color: #000000; background-color: #ffffff;">"</span><span style="color: #8b2252;">({</span>
<span style="color: #8b2252;">        "feature-x-enabled": true,</span>
<span style="color: #8b2252;">        "value-of-y": 1729,</span>
<span style="color: #8b2252;">        "z-options": {"a": null,</span>
<span style="color: #8b2252;">                      "b": "220 and 284",</span>
<span style="color: #8b2252;">                      "c": [6, 28, 496]}</span>
<span style="color: #8b2252;">       })</span><span style="color: #000000; background-color: #ffffff;">"</span>_json;
<span style="color: #a020f0;">if</span> <span style="color: #a020f0;">constexpr</span> (jsv[<span style="color: #8b2252;">"feature-x-enabled"</span>]) {
  <span style="color: #006400;">// </span><span style="color: #006400;">code for feature x</span>
} <span style="color: #a020f0;">else</span> {
  <span style="color: #006400;">// </span><span style="color: #006400;">code when feature x turned off</span>
}
</pre>
</div>

<aside class="notes">
<p>
When I first heard about <code>constexpr</code> I immediately thought of the potential for
this: generating compile-time data structures with UDLs. And JSON is an obvious
choice for a proof-of-concept.
</p>

<p>
Why JSON?
</p>
<ul>
<li>not too difficult (small grammar, well known)</li>
<li>sufficiently interesting (deal with recursive structure at compile time
without memory management)</li>
<li>ubiquitous, useful?</li>
<li>a bellwether for what is possible with <code>constepxr</code></li>

</ul>

</aside>

</section>
</section>
<section>
<section id="slide-org6d22465">
<h2 id="org6d22465">The Promise of <code>constexpr</code></h2>
<ul>
<li>Runtime efficiency</li>
<li>Clearer code, fewer magic numbers</li>
<li>Less cross-platform pain</li>

</ul>

<aside class="notes">
<p>
Jason talks about this.
</p>

<p>
Doing work at compile-time instead of runtime. Obvious gain.
</p>

<p>
Simplifying code through compile-time computation. No need for manual math,
preprocessor computation "to be sure", magic numbers.
</p>

<p>
Reducing steps in the toolchain. Don't maintain generation scripts: put it in
the C++.
</p>

</aside>

</section>
</section>
<section>
<section id="slide-org3d00060">
<h2 id="org3d00060"><code>constexpr</code> History 101</h2>
<p>
A Short, Incomplete (and Mostly Wrong?) History of <code>constexpr</code>
</p>

<aside class="notes">
<p>
Ben to drive this section.
</p>

</aside>

</section>
<section id="slide-org5f5aa96">
<h3 id="org5f5aa96">Three ages of <code>constexpr</code></h3>
<ul>
<li class="fragment appear">First age: C++11
<ul>
<li>One (<code>return</code>) expression per function was allowed</li>
<li>Recursion! math functions, FNV1 string hash, etc</li>

</ul></li>
<li class="fragment appear">Second age: C++14
<ul>
<li>Generalized <code>constexpr</code></li>
<li>Murmur3 hash, <code>constexpr</code> libraries appearing</li>

</ul></li>
<li class="fragment appear">Third age: C++17 and beyond
<ul>
<li><code>if constexpr</code> for metaprogramming</li>
<li><code>constexpr</code> lambdas, STL</li>
<li><code>constexpr</code> by default?</li>

</ul></li>

</ul>

<aside class="notes">
<p>
C++11 constexpr was "extreme recursion" but many things were doable nonetheless.
Scott Schurr's talks at CppNow/CppCon hinted at things to come and expounded on
the throw trick for forcing compile-time evaluation. (Explain)
</p>

<p>
For some reason, the major application of <code>constexpr</code> reported in the mainstream
seems to be string hashing.
</p>

<p>
<code>constexpr</code> lambdas are a really powerful thing (as we shall see).
<code>if constexpr</code> replaces many <code>std::enable_if</code> uses, more.
A selection of interesting <code>constexpr</code> things in the STL: <code>string_view</code>,
<code>array</code>, almost all of <code>chrono</code>.
New STL features are born with <code>constexpr</code> (somewhat) in mind: <code>optional</code>,
<code>variant</code>.
</p>

</aside>

</section>
</section>
<section>
<section id="slide-org9c795a9">
<h2 id="org9c795a9">A problem with <code>constexpr</code></h2>

<div class="figure">
<p><img src="./constexpr_problem.png" alt="constexpr_problem.png" />
</p>
</div>

<p>
The inability to use different runtime and compile time algorithms.
</p>

<p>
You <b>can</b> try to SFINAE on <code>constexpr</code>, but it's messy and brittle. YMMV.
</p>

<aside class="notes">
<p>
We will come to proposals later.
</p>

</aside>

</section>
</section>
<section>
<section id="slide-org2e57a98">
<h2 id="org2e57a98">Building <code>constexpr</code> JSON Values</h2>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsv</span>
  = R<span style="color: #000000; background-color: #ffffff;">"</span><span style="color: #8b2252;">({</span>
<span style="color: #8b2252;">        "feature-x-enabled": true,</span>
<span style="color: #8b2252;">        "value-of-y": 1729,</span>
<span style="color: #8b2252;">        "z-options": {"a": null,</span>
<span style="color: #8b2252;">                      "b": "220 and 284",</span>
<span style="color: #8b2252;">                      "c": [6, 28, 496]}</span>
<span style="color: #8b2252;">       })</span><span style="color: #000000; background-color: #ffffff;">"</span>_json;
</pre>
</div>

<p>
Two problems to solve:
</p>

<ol>
<li>How to represent JSON values</li>
<li>How to parse JSON values</li>

</ol>

</section>
</section>
<section>
<section id="slide-org4d4c5c6">
<h2 id="org4d4c5c6">Representing JSON Values</h2>
<p>
A JSON Value is a discriminated union of:<br />
<br />
</p>
<ul>
<li class="fragment appear">null</li>
<li class="fragment appear">boolean</li>
<li class="fragment appear">number</li>
<li class="fragment appear">string</li>
<li class="fragment appear">array of values</li>
<li class="fragment appear">object (map of string → value)</li>

</ul>

<p class="fragment (appear)">
<br />
Clearly this is going to need some sort of recursion. And we are going to need
<code>constexpr</code> ways to deal with a string, a vector and a map.
</p>

<aside class="notes">
<p>
Jason to drive this section.
</p>

</aside>

</section>
<section id="slide-orgbc52b92">
<h3 id="orgbc52b92"><code>constexpr</code> strings</h3>
<p>
<br />
First, <code>std::string_view</code> is great, and <i>mostly</i> <code>constexpr</code><br />
(depending on how up-to-date your library implementation is).<br />
<br />
<br />
Of course, <code>std::string_view</code> only really handles literal values:<br />
it doesn't deal with building strings, and is not intended for <i>storing</i> strings.
</p>

<aside class="notes">
<p>
<code>string_view</code> comparison is not yet <code>constexpr</code>.
</p>

</aside>

</section>
<section id="slide-org53fc63c">
<h3 id="org53fc63c"><code>constexpr</code> strings</h3>
<p>
<br />
We need a way to pass, store, and in general, work with<br />
character string literals.<br />
<br />
<br />
While <code>std::string_view</code> would technically work for this<br />
it kind of mixes metaphors, since it is not intended for storing<br />
and comparison - just viewing.<br />
<br />
<br />
For this, we built up the <code>static_string</code> class.
</p>

</section>
<section id="slide-org810af1f">
<h3 id="org810af1f"><code>constexpr</code> strings</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">static_string</span>
{
  <span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">N</span>&gt;
  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">static_string</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">char</span> (&amp;<span style="color: #a0522d;">str</span>)[N])
    : m_size(N-1), m_data(&amp;str[0])
  {}

  <span style="color: #006400;">// </span><span style="color: #006400;">constructor for substrings of string literals</span>
  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">static_string</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">char</span>* <span style="color: #a0522d;">str</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">s</span>)
    : m_size(s), m_data(str)
  {}

  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">static_string</span>() = <span style="color: #a020f0;">default</span>;

  <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">size_t</span> <span style="color: #0000ff;">size</span>() <span style="color: #a020f0;">const</span> { <span style="color: #a020f0;">return</span> m_size; }
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">const</span> <span style="color: #228b22;">char</span> *<span style="color: #0000ff;">c_str</span>() <span style="color: #a020f0;">const</span> { <span style="color: #a020f0;">return</span> m_data; }

  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">m_size</span>{0};
  <span style="color: #a020f0;">const</span> <span style="color: #228b22;">char</span> *<span style="color: #a0522d;">m_data</span> = <span style="color: #008b8b;">nullptr</span>;
};
</pre>
</div>

</section>
<section id="slide-orged44691">
<h3 id="orged44691"><code>constexpr</code> vectors</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">Value</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Size</span> = 5&gt;
<span style="color: #a020f0;">class</span> <span style="color: #228b22;">vector</span>
{
  <span style="color: #a020f0;">using</span> <span style="color: #228b22;">storage_t</span> = <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">array</span>&lt;<span style="color: #228b22;">Value</span>, Size&gt;;
  <span style="color: #228b22;">storage_t</span> <span style="color: #a0522d;">m_data</span>{};
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">m_size</span>{0};
  <span style="color: #0000ff;">...</span>

  <span style="color: #006400;">// </span><span style="color: #006400;">iterators, push_back, operator[] etc</span>
  <span style="color: #006400;">// </span><span style="color: #006400;">are pretty easy to write</span>
}
</pre>
</div>

<aside class="notes">
<p>
Obviously we need to know the max size at compile time.
</p>

</aside>

</section>
<section id="slide-orgc461c58">
<h3 id="orgc461c58"><code>constexpr</code> vectors</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">using</span> <span style="color: #228b22;">iterator</span> = <span style="color: #a020f0;">typename</span> <span style="color: #008b8b;">storage_t</span>::iterator;
<span style="color: #a020f0;">using</span> <span style="color: #228b22;">const_iterator</span> = <span style="color: #a020f0;">typename</span> <span style="color: #008b8b;">storage_t</span>::const_iterator;

<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">begin</span>() <span style="color: #a020f0;">const</span> { <span style="color: #a020f0;">return</span> m_data.begin(); }
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">end</span>() <span style="color: #a020f0;">const</span> { <span style="color: #a020f0;">return</span> m_data.begin() + m_size; }
<span style="color: #006400;">// </span><span style="color: #006400;">and similarly for other iterator functions...</span>

<span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">void</span> <span style="color: #0000ff;">push_back</span>(<span style="color: #228b22;">Value</span> <span style="color: #a0522d;">t_v</span>)
{
  <span style="color: #a020f0;">if</span> (m_size &gt;= Size) {
    <span style="color: #a020f0;">throw</span> <span style="color: #008b8b;">std</span>::range_error(<span style="color: #8b2252;">"Index past end of vector"</span>);
  } <span style="color: #a020f0;">else</span> {
    m_data[m_size++] = <span style="color: #008b8b;">std</span>::move(t_v);
  }
}
</pre>
</div>

<p>
We were not able to use <code>std::next()</code> here, seems to be a bug in the implementation&#x2026;
</p>

<aside class="notes">
<p>
Note that the <code>throw</code> here is a nicety: if we were to read/write past the end of
a <code>constexpr</code> array the compiler would give an error anyway. Assuming we are working
in a <code>constexpr</code> context. This throw protects us if this class is used just for a handy
statically sized vector.
</p>

</aside>

</section>
<section id="slide-org9c725cd">
<h3 id="org9c725cd">Why not <code>std::next</code>?</h3>
<p>
In GCC 7.2's implementation: internal <code>__iterator_category</code> is not <code>constexpr</code> constructible.
</p>

<iframe width="1400px" height="600px" src="https://godbolt.org/g/4YBTN7"></iframe>

</section>
<section id="slide-orga53d4b8">
<h3 id="orga53d4b8"><code>constexpr</code> vectors</h3>
<p>
This allows for natural use of the <code>vector</code> type
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">int</span>&gt; <span style="color: #a0522d;">vec</span>;
vec.push_back(15);
</pre>
</div>

</section>
<section id="slide-org30ae73f">
<h3 id="org30ae73f"><code>constexpr</code> vectors</h3>
<p>
Or put into a <code>constexpr</code> context
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">get_vector</span>() {
  <span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">int</span>&gt; <span style="color: #a0522d;">vec</span>;
  vec.push_back(15);
  <span style="color: #a020f0;">return</span> vec;
}

<span style="color: #228b22;">int</span> <span style="color: #0000ff;">main</span>() {
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">a_vector</span> = get_vector();
  <span style="color: #a020f0;">static_assert</span>(a_vector.size() == 1);
}
</pre>
</div>

</section>
<section id="slide-orgee1db06">
<h3 id="orgee1db06">mutable <code>constexpr</code> strings</h3>
<p>
And now we can build a mutable <code>constexpr</code> string by inheriting from our <code>vector</code>
</p>

</section>
<section id="slide-org1f7bb10">
<h3 id="org1f7bb10">mutable <code>constexpr</code> strings</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">CharType</span>, <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Size</span>&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">basic_string</span> : <span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">CharType</span>, Size&gt;
{
  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">basic_string</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">static_string</span> &amp;<span style="color: #a0522d;">s</span>) 
    : vector&lt;<span style="color: #228b22;">CharType</span>, Size&gt;(s.begin(), s.end())
  {}
  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">basic_string</span>(<span style="color: #a020f0;">const</span> <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> &amp;<span style="color: #a0522d;">s</span>)
    : vector&lt;<span style="color: #228b22;">CharType</span>, Size&gt;(s.cbegin(), s.cend())
  {}
  <span style="color: #006400;">// </span><span style="color: #006400;">...</span>
};
</pre>
</div>

<p>
This relies on:
</p>
<ul>
<li><code>constexpr</code> data members must be initialized, so our base vector is all <code>0</code></li>
<li>We have not provided any methods for shrinking our data structures, but that is possible</li>

</ul>

</section>
<section id="slide-orgae8367a">
<h3 id="orgae8367a"><code>constexpr</code> maps</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">Key</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">Value</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Size</span> = 5&gt;
<span style="color: #a020f0;">class</span> <span style="color: #228b22;">map</span>
{
  <span style="color: #a020f0;">using</span> <span style="color: #228b22;">storage_t</span> = <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">array</span>&lt;<span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">pair</span>&lt;<span style="color: #228b22;">Key</span>, <span style="color: #228b22;">Value</span>&gt;, Size&gt;;
  <span style="color: #228b22;">storage_t</span> <span style="color: #a0522d;">m_data</span>{};
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">m_size</span>{0};
  <span style="color: #0000ff;">...</span>

  <span style="color: #006400;">// </span><span style="color: #006400;">iterators are the same as for arrays</span>
  <span style="color: #006400;">// </span><span style="color: #006400;">operator[] needs a constexpr find</span>
  <span style="color: #006400;">// </span><span style="color: #006400;">data grows in the same way that vector does</span>
}
</pre>
</div>

</section>
<section id="slide-org434686e">
<h3 id="org434686e"><code>constexpr</code> maps</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">get_colors</span>() {
  <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">map</span>&lt;<span style="color: #008b8b;">cx</span>::static_string, <span style="color: #008b8b;">std</span>::uint32_t&gt; <span style="color: #a0522d;">colors</span>;
  colors[<span style="color: #8b2252;">"red"</span>] = <span style="color: #a020f0;">0x</span><span style="color: #008b8b;">FF0000</span>;
  colors[<span style="color: #8b2252;">"green"</span>] = <span style="color: #a020f0;">0x</span><span style="color: #008b8b;">00FF00</span>;
  <span style="color: #a020f0;">return</span> colors;
}

<span style="color: #228b22;">int</span> <span style="color: #0000ff;">main</span>() {
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">colors</span> = get_colors();
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">r</span> = colors[<span style="color: #8b2252;">"red"</span>]; <span style="color: #006400;">// </span><span style="color: #006400;">returns 0xFF0000</span>
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">b</span> = colors[<span style="color: #8b2252;">"blue"</span>]; <span style="color: #006400;">// </span><span style="color: #006400;">compile-time error</span>
}
</pre>
</div>

</section>
<section id="slide-orga54a27e">
<h3 id="orga54a27e">Why not <code>std::pair</code>?</h3>
<p>
Standard library definition does not have<br />
<code>constexpr operator=</code> for <code>std::pair</code><br />
This is the only aspect of <code>std::pair</code> that is not <code>constexpr</code>
</p>

<iframe width="1400px" height="600px" src="https://godbolt.org/g/brM8Ec"></iframe>

</section>
<section id="slide-org0262b57">
<h3 id="org0262b57"><code>constexpr find_if</code></h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">InputIt</span>, <span style="color: #a020f0;">class</span> <span style="color: #228b22;">UnaryPredicate</span>&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">InputIt</span> <span style="color: #0000ff;">find_if</span>(<span style="color: #228b22;">InputIt</span> <span style="color: #a0522d;">first</span>, <span style="color: #228b22;">InputIt</span> <span style="color: #a0522d;">last</span>, <span style="color: #228b22;">UnaryPredicate</span> <span style="color: #a0522d;">p</span>)
{
  <span style="color: #a020f0;">for</span> (; first != last; ++first) {
    <span style="color: #a020f0;">if</span> (p(*first)) {
      <span style="color: #a020f0;">return</span> first;
    }
  }
  <span style="color: #a020f0;">return</span> last;
}
</pre>
</div>

<aside class="notes">
<p>
There's no technical reason for many algorithms not to be <code>constexpr</code>.
</p>

</aside>

</section>
<section id="slide-org0f5e07d">
<h3 id="org0f5e07d">Let's make them all <code>constexpr</code> already</h3>

<div class="figure">
<p><img src="./bryce_tweet.png" alt="bryce_tweet.png" />
</p>
</div>

<p>
(Bryce said we can't have <code>constexpr</code> parallel algorithms, though. ;_;)
</p>

</section>
<section id="slide-orgb7cd925">
<h3 id="orgb7cd925">Other algorithms we made <code>constexpr</code></h3>
<ul>
<li><code>mismatch</code></li>
<li><code>equal</code></li>
<li><code>copy</code></li>

</ul>

<p>
In the course of implementing this talk, we found uses for several <code>constexpr</code>
algorithms.
</p>

</section>
<section id="slide-org583db03">
<h3 id="org583db03">JSON Value: First attempt</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span>=5&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">max_vector_size</span>{6};
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">max_map_size</span>{6};

  <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Data</span>
  {
    <span style="color: #228b22;">bool</span> <span style="color: #a0522d;">boolean</span>{<span style="color: #008b8b;">false</span>};
    <span style="color: #228b22;">double</span> <span style="color: #a0522d;">number</span>{0};
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">static_string</span> <span style="color: #a0522d;">string</span>;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_vector_size&gt; <span style="color: #a0522d;">array</span>;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">map</span>&lt;<span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">static_string</span>, <span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_map_size&gt; <span style="color: #a0522d;">object</span>;
  };
  <span style="color: #a020f0;">enum</span> <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Type</span> { <span style="color: #a0522d;">Null</span>, <span style="color: #a0522d;">Boolean</span>, <span style="color: #a0522d;">Number</span>, <span style="color: #a0522d;">String</span>, <span style="color: #a0522d;">Array</span>, <span style="color: #a0522d;">Object</span> };

  <span style="color: #228b22;">Type</span> <span style="color: #a0522d;">type</span> = <span style="color: #008b8b;">Type</span>::Null;
  <span style="color: #228b22;">Data</span> <span style="color: #a0522d;">data</span>;
  <span style="color: #0000ff;">...</span>
};

<span style="color: #a020f0;">template</span> &lt;&gt; <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>&lt;0&gt; {};
</pre>
</div>

<aside class="notes">
<p>
This makes for a lot of template instantiations, and has some obvious limitations.
</p>

<p>
The max sizes for arrays and objects are determined empirically.
</p>

<p>
We use <code>struct</code> here initially, but <code>union</code> later.
</p>

</aside>

</section>
<section id="slide-org53a0011">
<h3 id="org53a0011">JSON Value: First attempt</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">void</span> <span style="color: #0000ff;">assert_type</span>(<span style="color: #228b22;">Type</span> <span style="color: #a0522d;">t</span>) <span style="color: #a020f0;">const</span>
  {
    <span style="color: #a020f0;">if</span> (type != t) <span style="color: #a020f0;">throw</span> <span style="color: #008b8b;">std</span>::runtime_error(<span style="color: #8b2252;">"Incorrect type"</span>);
  }

  <span style="color: #006400;">// </span><span style="color: #006400;">For Array, and similarly for the other types</span>
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">decltype</span>(<span style="color: #a020f0;">auto</span>) <span style="color: #0000ff;">to_Array</span>() <span style="color: #a020f0;">const</span>
  {
    assert_type(<span style="color: #008b8b;">Type</span>::Array);
    <span style="color: #a020f0;">return</span> (data.array);
  }
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">decltype</span>(<span style="color: #a020f0;">auto</span>) <span style="color: #0000ff;">to_Array</span>()
  {
    <span style="color: #a020f0;">if</span> (type != <span style="color: #008b8b;">Type</span>::Array) {
      type = <span style="color: #008b8b;">Type</span>::Array;
      data.array = {};
    }
    <span style="color: #a020f0;">return</span> (data.array);
  }
};
</pre>
</div>

</section>
<section id="slide-org9daef96">
<h3 id="org9daef96">JSON Value: First attempt</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">JSON_Value</span> <span style="color: #a0522d;">j</span>{};
j[<span style="color: #8b2252;">"a"</span>].to_Number() = 15;
j[<span style="color: #8b2252;">"b"</span>].to_String() = <span style="color: #8b2252;">"Hello World"</span>;
j[<span style="color: #8b2252;">"d"</span>].to_Array();
j[<span style="color: #8b2252;">"c"</span>][<span style="color: #8b2252;">"a"</span>][<span style="color: #8b2252;">"b"</span>].to_Array().push_back(10.0);
j[<span style="color: #8b2252;">"c"</span>][<span style="color: #8b2252;">"a"</span>][<span style="color: #8b2252;">"c"</span>] = <span style="color: #008b8b;">cx</span>::static_string(<span style="color: #8b2252;">"Hello World"</span>);
j[<span style="color: #8b2252;">"c"</span>][<span style="color: #8b2252;">"a"</span>][<span style="color: #8b2252;">"d"</span>].to_Array().push_back(5.2);
</pre>
</div>

<aside class="notes">
<p>
But this kind of thing works. Note that we are using C++17 class template type
deduction here so we don't need to say <code>cx::JSON_Value&lt;&gt; j{};</code>
</p>

</aside>

</section>
<section id="slide-orgd68fdb5">
<h3 id="orgd68fdb5">Why not <code>std::variant</code> ?</h3>
<p>
Similarly to <code>std::pair</code>, <code>std::variant</code> is missing some key <code>constexpr</code> support.
</p>

<ul>
<li class="fragment appear"><code>std::variant(const std::variant &amp;)</code></li>
<li class="fragment appear"><code>std::variant(std::variant &amp;&amp;)</code></li>
<li class="fragment appear"><code>std::variant &amp;operator=(const std::variant &amp;)</code></li>
<li class="fragment appear"><code>std::variant &amp;operator=(std::variant &amp;&amp;)</code></li>

</ul>

</section>
<section id="slide-org46a27ea">
<h3 id="org46a27ea">Requirements for compile-time types</h3>
<p>
Huge list! Are you ready?! 
</p>

<ul>
<li class="fragment appear"><code>constexpr</code> constructor</li>
<li class="fragment appear"><code>std::is_trivially_destructible</code></li>

</ul>

<p class="fragment (appear)">
Nothing else is required if it does not get invoked.
</p>

</section>
<section id="slide-org345f814">
<h3 id="org345f814">STL shortcomings</h3>
<ul>
<li><code>array</code></li>
<li><code>string</code></li>
<li><code>string_view</code></li>
<li><code>pair</code></li>
<li><code>optional</code></li>
<li><code>variant</code></li>
<li><code>swap</code></li>

</ul>

<aside class="notes">
<p>
Many of these parts of the STL have <code>constexpr</code> desires and partially
<code>constexpr</code> friendly implementations.
</p>

<p>
In our experience, none of them quite achieves everything that is possibly
<code>constexpr</code>. In many cases this could just be an oversight in the implementation
or the standard and not because of some deep reason.
</p>

</aside>

</section>
<section id="slide-orgf1b3f08">
<h3 id="orgf1b3f08">Limitations of our containers</h3>
<ul>
<li>Fixed maximum size</li>
<li>(Currently) cannot shrink</li>
<li>Requires types that are default constructible</li>

</ul>

</section>
<section id="slide-orgb393140">
<h3 id="orgb393140">How to improve our containers</h3>
<ul>
<li>We could wrap objects in <code>std::optional</code> to allow for objects that are not default constructible</li>
<li>It should be possible to templatize on <code>constexpr</code> enabled allocator, making these containers optionally <code>constexpr</code></li>

</ul>

</section>
<section id="slide-orgde5fc19">
<h3 id="orgde5fc19"><code>constexpr</code> allocator?</h3>
<p>
From cppreference.com
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">SimpleAllocator</span> {
  <span style="color: #a020f0;">typedef</span> <span style="color: #228b22;">T</span> <span style="color: #228b22;">value_type</span>;
  <span style="color: #0000ff;">SimpleAllocator</span>(<span style="color: #006400;">/*</span><span style="color: #006400;">ctor args*/</span>);
  <span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">U</span>&gt; <span style="color: #0000ff;">SimpleAllocator</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">SimpleAllocator</span>&lt;<span style="color: #228b22;">U</span>&gt;&amp; <span style="color: #a0522d;">other</span>);
  <span style="color: #228b22;">T</span>* <span style="color: #0000ff;">allocate</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">n</span>);
  <span style="color: #228b22;">void</span> <span style="color: #0000ff;">deallocate</span>(<span style="color: #228b22;">T</span>* <span style="color: #a0522d;">p</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">n</span>);
};
<span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">T</span>, <span style="color: #a020f0;">class</span> <span style="color: #228b22;">U</span>&gt;
<span style="color: #228b22;">bool</span> <span style="color: #a020f0;">operator</span><span style="color: #0000ff;">==</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">SimpleAllocator</span>&lt;<span style="color: #228b22;">T</span>&gt;&amp;, <span style="color: #a020f0;">const</span> <span style="color: #228b22;">SimpleAllocator</span>&lt;<span style="color: #228b22;">U</span>&gt;&amp;);
<span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">T</span>, <span style="color: #a020f0;">class</span> <span style="color: #228b22;">U</span>&gt;
<span style="color: #228b22;">bool</span> <span style="color: #a020f0;">operator</span><span style="color: #0000ff;">!=</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">SimpleAllocator</span>&lt;<span style="color: #228b22;">T</span>&gt;&amp;, <span style="color: #a020f0;">const</span> <span style="color: #228b22;">SimpleAllocator</span>&lt;<span style="color: #228b22;">U</span>&gt;&amp;);
</pre>
</div>

</section>
<section id="slide-org696c935">
<h3 id="org696c935"><code>constexpr</code> allocator?</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">T</span>, <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Size</span>&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">ConstexprAllocator</span> {
  <span style="color: #a020f0;">typedef</span> <span style="color: #228b22;">T</span> <span style="color: #228b22;">value_type</span>;
  <span style="color: #228b22;">consstexpr</span> <span style="color: #0000ff;">ConstexprAllocator</span>(<span style="color: #006400;">/*</span><span style="color: #006400;">ctor args*/</span>);
  <span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">class</span> <span style="color: #228b22;">U</span>&gt; 
  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">ConstexprAllocator</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">ConstexprAllocator</span>&lt;<span style="color: #228b22;">U</span>&gt;&amp; <span style="color: #a0522d;">other</span>);
  <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">T</span>* <span style="color: #0000ff;">allocate</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">n</span>);
  <span style="color: #a020f0;">constexpr</span>  <span style="color: #228b22;">void</span> <span style="color: #0000ff;">deallocate</span>(<span style="color: #228b22;">T</span>* <span style="color: #a0522d;">p</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">n</span>);
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">array</span>&lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">pair</span>&lt;<span style="color: #228b22;">bool</span>, <span style="color: #228b22;">value_type</span>&gt;, Size&gt; <span style="color: #a0522d;">data</span>; <span style="color: #006400;">// </span><span style="color: #006400;">bool for free flag</span>
};
</pre>
</div>

<p>
Implementation left as an exercise to the reader.
</p>

</section>
</section>
<section>
<section id="slide-org868267f">
<h2 id="org868267f">Parsing JSON Value Literals</h2>
<p>
Because we need some way to actually turn a string literal into our JSON
representation.
</p>

<aside class="notes">
<p>
Ben drives this section.
</p>

</aside>

</section>
<section id="slide-org580de02">
<h3 id="org580de02">What is a Parser?</h3>
<p>
<br />
</p>
<div class="org-src-container">

<pre  class="src src-haskell"><span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">::</span> <span style="color: #228b22;">String</span> <span style="color: #a0522d;">-&gt;</span> [(a, <span style="color: #228b22;">String</span>)]
</pre>
</div>
<p>
"A parser for things is a function from strings to lists of pairs of things and strings."
</p>

<p>
&#x2013; <a href="http://www.willamette.edu/~fruehr/haskell/seuss.html">Dr Seuss on parsers</a><br />
<br />
<br />
Or in our case something like:
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">using</span> <span style="color: #228b22;">parser</span> = <span style="color: #a020f0;">auto</span> (*)(string) -&gt; <span style="color: #228b22;">list</span>&lt;<span style="color: #228b22;">pair</span>&lt;<span style="color: #228b22;">T</span>, <span style="color: #228b22;">string</span>&gt;&gt;;
</pre>
</div>

<aside class="notes">
<p>
This serendipitous phrase is due to Fritz Ruehr, a functional programming
lecturer at Willamette University.
</p>

</aside>

</section>
<section id="slide-orgfab18de">
<h3 id="orgfab18de">Parsers</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">using</span> <span style="color: #228b22;">parser</span> = <span style="color: #a020f0;">auto</span> (*)(string) -&gt; <span style="color: #228b22;">list</span>&lt;<span style="color: #228b22;">pair</span>&lt;<span style="color: #228b22;">T</span>, <span style="color: #228b22;">string</span>&gt;&gt;;
</pre>
</div>

<p>
Of course, we don't really mean quite this&#x2026;
</p>

<ul>
<li class="fragment appear"><code>string</code> ⇒ <code>string_view</code> (compile-time stringlike thing)</li>
<li class="fragment appear"><code>list</code> ⇒ <code>optional</code> (simpler)</li>
<li class="fragment appear">"function" ⇒ "something invocable"</li>

</ul>

<aside class="notes">
<p>
Strings are any stringlike thing - <code>string_view</code> will do nicely since we're just
reading this from a literal. The input is obvious, the output is the leftover
part of the string after parsing a T.
</p>

<p>
List represents optionality - a given string might have several ways it can be
parsed. For simplicity we can just assume one way or error, i.e. optional.
</p>

<p>
Of course we'll use the <code>constexpr</code> friendly <code>pair</code>.
</p>

<p>
And when we say "function" we mean the usual invocable things. Including <code>constexpr</code>
lambdas!
</p>

</aside>

</section>
<section id="slide-org9e01433">
<h3 id="org9e01433">A Simple Parser</h3>
<p>
Let's have a couple of aliases that will make life simpler.
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">using</span> <span style="color: #228b22;">parse_input_t</span> = <span style="color: #008b8b;">std</span>::string_view;

<span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">using</span> <span style="color: #228b22;">parse_result_t</span> = <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">optional</span>&lt;<span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">pair</span>&lt;<span style="color: #228b22;">T</span>, <span style="color: #228b22;">parse_input_t</span>&gt;&gt;;
</pre>
</div>

<p>
And let's make a parser that matches a single <code>char</code> that we give it.
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">match_char</span>(<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>, <span style="color: #228b22;">char</span> <span style="color: #a0522d;">c</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">char</span>&gt;
{
  <span style="color: #a020f0;">if</span> (s.empty() || s[0] != c) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
  <span style="color: #a020f0;">return</span> parse_result_t&lt;<span style="color: #228b22;">char</span>&gt;(
    <span style="color: #008b8b;">cx</span>::make_pair(c, parse_input_t(s.data()+1, s.size()-1)));
}
</pre>
</div>

<aside class="notes">
<p>
This is what a parser does: either matches or not (hence the optional) and if it
matches, returns the value matched and the rest of the string for use in future
parsers.
</p>

</aside>

</section>
<section id="slide-orgcd2fd3c">
<h3 id="orgcd2fd3c">A Simple Parser</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #006400;">// </span><span style="color: #006400;">Ceci n'est pas un parser.</span>
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">match_char</span>(<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>, <span style="color: #228b22;">char</span> <span style="color: #a0522d;">c</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">char</span>&gt;;
</pre>
</div>

<p>
<code>match_char</code> isn't actually a parser, because it has the wrong signature.<br />
<br />
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #006400;">// </span><span style="color: #006400;">This is the signature of a parser.</span>
<span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">using</span> <span style="color: #228b22;">parser</span> = <span style="color: #a020f0;">auto</span> (*)(<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">T</span>&gt;;
</pre>
</div>

<p>
But now that we have <code>constexpr</code> lambdas, we can write a function that returns a
parser.
</p>

</section>
<section id="slide-org5833206">
<h3 id="org5833206">A Simple Parser</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">make_char_parser</span>(<span style="color: #228b22;">char</span> <span style="color: #a0522d;">c</span>)
{
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">char</span>&gt; {
    <span style="color: #a020f0;">if</span> (s.empty() || s[0] != c) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
    <span style="color: #a020f0;">return</span> parse_result_t&lt;<span style="color: #228b22;">char</span>&gt;(
        <span style="color: #008b8b;">cx</span>::make_pair(c, parse_input_t(s.data()+1, s.size()-1)));
  };
}
</pre>
</div>
<p>
The lambda returned from <code>make_char_parser</code> is a parser that will match the
given <code>char</code>.
</p>

<aside class="notes">
<p>
Note that the lambda signature does NOT have to say constexpr: it's implicit.
</p>

</aside>

</section>
<section id="slide-org336cc88">
<h3 id="org336cc88">More useful primitive parsers</h3>
<p>
So far we can match one <code>char</code>. Because fundamentally parsing works on
"strings", there are a couple of other parsers that will be useful.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #006400;">// </span><span style="color: #006400;">parse one of a set of chars</span>
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">one_of</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> <span style="color: #a0522d;">chars</span>)
{
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">char</span>&gt; {
    <span style="color: #a020f0;">if</span> (s.empty()) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
    <span style="color: #006400;">// </span><span style="color: #006400;">basic_string_view::find is supposed to be constexpr, but no...</span>
    <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">j</span> = <span style="color: #008b8b;">cx</span>::find(chars.cbegin(), chars.cend(), s[0]);
    <span style="color: #a020f0;">if</span> (j != chars.cend()) {
      <span style="color: #a020f0;">return</span> parse_result_t&lt;<span style="color: #228b22;">char</span>&gt;(
          <span style="color: #008b8b;">cx</span>::make_pair(s[0], parse_input_t(s.data()+1, s.size()-1)));
    }
    <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
  };
}
</pre>
</div>

</section>
<section id="slide-org641f430">
<h3 id="org641f430">More useful primitive parsers</h3>
<p>
And you can imagine how to write these.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #006400;">// </span><span style="color: #006400;">the opposite of one_of: match a char that isn't any of the given set</span>
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">none_of</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> <span style="color: #a0522d;">chars</span>)
{
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">char</span>&gt; {
    <span style="color: #0000ff;">...</span>
  };
}

<span style="color: #006400;">// </span><span style="color: #006400;">match a given string</span>
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">make_string_parser</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> <span style="color: #a0522d;">str</span>)
{
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span>&gt; {
    <span style="color: #006400;">// </span><span style="color: #006400;">here we could use a constexpr version of std::mismatch...</span>
    <span style="color: #0000ff;">...</span>
  };
}
</pre>
</div>

</section>
<section id="slide-orgf8b50bb">
<h3 id="orgf8b50bb">Building up</h3>
<p>
<br />
So far we have a few primitive parsers.<br />
<br />
<br />
In order to simply build up more complex parsers, we need to be able to<br />
<b>combine</b> parsers in various ways.
</p>

</section>
<section id="slide-org634edcb">
<h3 id="org634edcb">Building up</h3>
<p>
Some basic things we will want to do:
</p>

<ul>
<li>Change the result type of a parser (<code>fmap</code>)</li>
<li>Run one parser, then a second one based on what the first returned (<code>bind</code>)</li>
<li>Run one parser, and if it fails run another (<code>operator|</code>)</li>
<li>Run two parsers in succession and combine the outputs (<code>combine</code>)</li>

</ul>

<p>
(Pick your functional pattern: functor, monad, monoid, applicative&#x2026;)
</p>

<aside class="notes">
<p>
Some suggested names for the operations involved.
</p>

<p>
"Change the result type" = run a function on the result to turn it into something else.
</p>

<p>
<code>operator|</code> is the monoid operation (with the parser that always fails as the unit).
</p>

<p>
<code>combine</code> is the applicative operation.
</p>

<p>
I'll show you a few of these combinators so you can get a feel for them.
</p>

</aside>

</section>
<section id="slide-org9cf8d02">
<h3 id="org9cf8d02">Changing the result type (<code>fmap</code>)</h3>
<div class="org-src-container">

<pre  class="src src-haskell"><span style="color: #0000ff;">fmap</span> <span style="color: #a0522d;">::</span> (a <span style="color: #a0522d;">-&gt;</span> b) <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
</pre>
</div>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">F</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P</span>&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">fmap</span>(<span style="color: #228b22;">F</span>&amp;&amp; <span style="color: #a0522d;">f</span>, <span style="color: #228b22;">P</span>&amp;&amp; <span style="color: #a0522d;">p</span>)
{
  <span style="color: #a020f0;">using</span> <span style="color: #228b22;">R</span> = <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">result_of_t</span>&lt;F(<span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P</span>&gt;)&gt;&gt;;
  <span style="color: #a020f0;">return</span> [f = <span style="color: #008b8b;">std</span>::forward&lt;<span style="color: #228b22;">F</span>&gt;(f),
          p = <span style="color: #008b8b;">std</span>::forward&lt;<span style="color: #228b22;">P</span>&gt;(p)] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">i</span>) -&gt; R {
           <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span> r = p(i);
           <span style="color: #a020f0;">if</span> (!r) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
           <span style="color: #a020f0;">return</span> R(<span style="color: #008b8b;">cx</span>::make_pair(f(r-&gt;first), r-&gt;second));
         };
}
</pre>
</div>

<aside class="notes">
<p>
<code>parse_t</code> here is just a way of getting the parsed type back out of the parser
without all the optional/pair business.
</p>

<p>
Note what fmap returns is a parser.
</p>

<p>
Think about a simple case of turning a char into an int.
</p>

</aside>

</section>
<section id="slide-orge0ba02b">
<h3 id="orge0ba02b">Alternation (<code>operator|</code>)</h3>
<div class="org-src-container">

<pre  class="src src-haskell">operator<span style="color: #0000ff;">|</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> a
</pre>
</div>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P1</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P2</span>,
          <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">enable_if_t</span>&lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">is_same_v</span>&lt;<span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P1</span>&gt;, <span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P2</span>&gt;&gt;, <span style="color: #228b22;">int</span>&gt; = 0&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a020f0;">operator</span><span style="color: #0000ff;">|</span>(<span style="color: #228b22;">P1</span>&amp;&amp; <span style="color: #a0522d;">p1</span>, <span style="color: #228b22;">P2</span>&amp;&amp; <span style="color: #a0522d;">p2</span>) {
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">i</span>) {
    <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span> r1 = p1(i);
    <span style="color: #a020f0;">if</span> (r1) <span style="color: #a020f0;">return</span> r1;
    <span style="color: #a020f0;">return</span> p2(i);
  };
}
</pre>
</div>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">fail</span>(<span style="color: #228b22;">T</span>) {
  <span style="color: #a020f0;">return</span> [=] (parse_input_t) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">T</span>&gt; {
    <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
  };
}
</pre>
</div>

<aside class="notes">
<p>
Alternation is the monoid operation. <code>fail</code> is the identity.
</p>

</aside>

</section>
<section id="slide-orgf49eedc">
<h3 id="orgf49eedc">Conjunction (<code>combine</code>)</h3>
<div class="org-src-container">

<pre  class="src src-haskell"><span style="color: #0000ff;">combine</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b <span style="color: #a0522d;">-&gt;</span> (a <span style="color: #a0522d;">-&gt;</span> b <span style="color: #a0522d;">-&gt;</span> c) <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> c
</pre>
</div>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P1</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P2</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">F</span>,
          <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">R</span> = <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">result_of_t</span>&lt;F(<span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P1</span>&gt;, <span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P2</span>&gt;)&gt;&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">combine</span>(<span style="color: #228b22;">P1</span>&amp;&amp; <span style="color: #a0522d;">p1</span>, <span style="color: #228b22;">P2</span>&amp;&amp; <span style="color: #a0522d;">p2</span>, <span style="color: #228b22;">F</span>&amp;&amp; <span style="color: #a0522d;">f</span>) {
  <span style="color: #a020f0;">return</span> [=] (<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">i</span>) -&gt; <span style="color: #228b22;">parse_result_t</span>&lt;<span style="color: #228b22;">R</span>&gt; {
           <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span> r1 = p1(i);
           <span style="color: #a020f0;">if</span> (!r1) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
           <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span> r2 = p2(r1-&gt;second);
           <span style="color: #a020f0;">if</span> (!r2) <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::nullopt;
           <span style="color: #a020f0;">return</span> parse_result_t&lt;<span style="color: #228b22;">R</span>&gt;(
               <span style="color: #008b8b;">cx</span>::make_pair(f(r1-&gt;first, r2-&gt;first), r2-&gt;second));
         };
}
</pre>
</div>

<aside class="notes">
<p>
<code>combine</code> is a bit like <code>fmap</code> for multiple-argument functions. In some sense
the applicative operation.
</p>

<p>
Note that both parsers need to succeed, and we run the second parser on what is
leftover from the first, then return what is leftover from the second.
</p>

</aside>

</section>
<section id="slide-org943680d">
<h3 id="org943680d">Useful <code>combine</code> patterns</h3>
<div class="org-src-container">

<pre  class="src src-haskell">operator<span style="color: #0000ff;">&gt;</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> a
operator<span style="color: #0000ff;">&lt;</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
</pre>
</div>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P1</span>, <span style="color: #a020f0;">typename</span> <span style="color: #228b22;">P2</span>,
          <span style="color: #a020f0;">typename</span> = <span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P1</span>&gt;, <span style="color: #a020f0;">typename</span> = <span style="color: #228b22;">parse_t</span>&lt;<span style="color: #228b22;">P2</span>&gt;&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a020f0;">operator</span><span style="color: #0000ff;">&lt;</span>(<span style="color: #228b22;">P1</span>&amp;&amp; <span style="color: #a0522d;">p1</span>, <span style="color: #228b22;">P2</span>&amp;&amp; <span style="color: #a0522d;">p2</span>) {
  <span style="color: #a020f0;">return</span> combine(<span style="color: #008b8b;">std</span>::forward&lt;<span style="color: #228b22;">P1</span>&gt;(p1),
                 <span style="color: #008b8b;">std</span>::forward&lt;<span style="color: #228b22;">P2</span>&gt;(p2),
                 [] (<span style="color: #a020f0;">auto</span>, <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span>&amp; <span style="color: #a0522d;">r</span>) { <span style="color: #a020f0;">return</span> r; });
}
</pre>
</div>

<p>
These operators are useful for throwing away the left or right hand side of <code>combine</code>.
</p>

<aside class="notes">
<p>
These simple formulations of combine are very useful. They allow us to run
multiple parsers in succession, keeping just the left hand side or the right
hand side.
</p>

<p>
And of course the operators are symmetric and left-associative.
</p>

</aside>

</section>
<section id="slide-org747d5da">
<h3 id="org747d5da">Accumulating combinators</h3>
<p>
And now you begin to see where this is heading&#x2026;
</p>

<div class="org-src-container">

<pre  class="src src-haskell"><span style="color: #0000ff;">many</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> b <span style="color: #a0522d;">-&gt;</span> (b <span style="color: #a0522d;">-&gt;</span> a <span style="color: #a0522d;">-&gt;</span> b)  <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
<span style="color: #0000ff;">many1</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> b <span style="color: #a0522d;">-&gt;</span> (b <span style="color: #a0522d;">-&gt;</span> a <span style="color: #a0522d;">-&gt;</span> b)  <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
<span style="color: #0000ff;">exactly_n</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> int <span style="color: #a0522d;">-&gt;</span> b <span style="color: #a0522d;">-&gt;</span> (b <span style="color: #a0522d;">-&gt;</span> a <span style="color: #a0522d;">-&gt;</span> b) <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
<span style="color: #0000ff;">separated_by</span> <span style="color: #a0522d;">::</span> <span style="color: #228b22;">Parser</span> a <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> x <span style="color: #a0522d;">-&gt;</span> b <span style="color: #a0522d;">-&gt;</span> (b <span style="color: #a0522d;">-&gt;</span> a <span style="color: #a0522d;">-&gt;</span> b) <span style="color: #a0522d;">-&gt;</span> <span style="color: #228b22;">Parser</span> b
</pre>
</div>

<p>
These are starting to look like building blocks we can use to parse real things.
</p>

<aside class="notes">
<p>
Explain each of these function signatures.
</p>

</aside>

</section>
<section id="slide-org7ada81a">
<h3 id="org7ada81a">Some simple examples</h3>
<p>
This parser eats whitespace.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">skip_whitespace</span>()
{
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">ws_parser</span> =
    make_char_parser(<span style="color: #8b2252;">' '</span>)
    | make_char_parser(<span style="color: #8b2252;">'\t'</span>)
    | make_char_parser(<span style="color: #8b2252;">'\n'</span>)
    | make_char_parser(<span style="color: #8b2252;">'\r'</span>);
  <span style="color: #a020f0;">return</span> many(ws_parser, <span style="color: #008b8b;">std</span>::monostate{}, [] (<span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">m</span>, <span style="color: #a020f0;">auto</span>) { <span style="color: #a020f0;">return</span> m; });
}
</pre>
</div>

<aside class="notes">
<p>
Alternation of each individual parser. (Also, we could use <code>one_of</code> here.)
</p>

<p>
Then many (zero or more) of the resulting parser.
</p>

<p>
The key to all the combinators is that what they return are themselves parsers.
Composition!
</p>

</aside>

</section>
<section id="slide-orga91ee16">
<h3 id="orga91ee16">Some simple examples</h3>
<p>
This parses a decimal integer.
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">int_parser</span>()
{
  <span style="color: #a020f0;">return</span> bind(one_of(<span style="color: #8b2252;">"123456789"</span><span style="color: #008b8b;">s</span>v),
              [] (<span style="color: #228b22;">char</span> <span style="color: #a0522d;">x</span>, <span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">rest</span>) {
                <span style="color: #a020f0;">return</span> many(one_of(<span style="color: #8b2252;">"0123456789"</span><span style="color: #008b8b;">s</span>v),
                            <span style="color: #a020f0;">static_cast</span>&lt;<span style="color: #228b22;">int</span>&gt;(x - <span style="color: #8b2252;">'0'</span>),
                            [] (<span style="color: #228b22;">int</span> <span style="color: #a0522d;">acc</span>, <span style="color: #228b22;">char</span> <span style="color: #a0522d;">c</span>) { <span style="color: #a020f0;">return</span> (<span style="color: #228b22;">acc</span>*10) + (c-<span style="color: #8b2252;">'0'</span>); })(rest);
              });
}
</pre>
</div>
<p>
First any non-zero digit, then zero or more digits,<br />
building up the integer in the obvious way.
</p>

<aside class="notes">
<p>
Note that <code>bind</code>'s second argument carries the leftover string through as well
as the parse result of the first argument.
</p>

</aside>

</section>
<section id="slide-org9e9b1c8">
<h3 id="org9e9b1c8">Some simple examples</h3>
<p>
This (very simply) parses a string.
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">string_parser</span>(<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>)
{
  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">quote_parser</span> = make_char_parser(<span style="color: #8b2252;">'"'</span>);
  <span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span> str_parser =
    many(none_of(<span style="color: #8b2252;">"\""</span><span style="color: #008b8b;">s</span>v),
         <span style="color: #008b8b;">std</span>::string_view(s.data()+1, 0),
         [] (<span style="color: #a020f0;">const</span> <span style="color: #a020f0;">auto</span>&amp; <span style="color: #a0522d;">acc</span>, <span style="color: #a020f0;">auto</span>) {
           <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">std</span>::string_view(acc.data(), acc.size()+1);
         });
  <span style="color: #a020f0;">return</span> (<span style="color: #228b22;">quote_parser</span> &lt; str_parser &gt; quote_parser)(s);
}
</pre>
</div>

<aside class="notes">
<p>
For the sake of simplicity, we aren't dealing with escaped characters, unicode
points, etc.
</p>

<p>
In fact for this simple example we are accumulating a <code>string_view</code>. But in
general when we come to parse escaped characters, the input characters don't
have a 1-to-1 mapping with the output characters.
</p>

</aside>

</section>
<section id="slide-org6da1730">
<h3 id="org6da1730">Getting to JSON</h3>
<p>
We now have a toolkit for building parsers.
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span>=5&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #0000ff;">...</span>
  <span style="color: #a020f0;">struct</span> Data
  {
    <span style="color: #228b22;">bool</span> <span style="color: #a0522d;">boolean</span>{<span style="color: #008b8b;">false</span>};
    <span style="color: #228b22;">double</span> <span style="color: #a0522d;">number</span>{0};
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">static_string</span> <span style="color: #a0522d;">string</span>;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_vector_size&gt; <span style="color: #a0522d;">array</span>;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">map</span>&lt;<span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">static_string</span>, <span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_map_size&gt; <span style="color: #a0522d;">object</span>;
  };
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>
<p>
To parse our JSON value, a reasonable approach is to use<br />
alternation on parsers for each type of value.
</p>

<aside class="notes">
<p>
We're going to have 6 different parsers, each of which produces a <code>JSON_Value</code>,
and we're going to alternate them together.
</p>

<p>
They will be mutually recursive: the parsers for objects and arrays call the
value parsers.
</p>

<p>
In order to achieve mutual recursion, we'll put them in a struct. (The next
couple of slides contain a lot of code - sorry.)
</p>

</aside>

</section>
<section id="slide-org4e934d5">
<h3 id="org4e934d5">Recursive parsing structure</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">recur</span>
{
  <span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span> = max_parse_depth&gt;
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">value_parser</span>()
  {
    <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">p</span> =
      fmap([] (<span style="color: #008b8b;">std</span>::string_view) { <span style="color: #a020f0;">return</span> JSON_Value&lt;Depth&gt;(<span style="color: #008b8b;">std</span>::monostate{}); },
           make_string_parser(<span style="color: #8b2252;">"null"</span><span style="color: #008b8b;">s</span>v))
      | fmap([] (<span style="color: #008b8b;">std</span>::string_view) { <span style="color: #a020f0;">return</span> JSON_Value&lt;Depth&gt;(<span style="color: #008b8b;">true</span>); },
             make_string_parser(<span style="color: #8b2252;">"true"</span><span style="color: #008b8b;">s</span>v))
      | fmap([] (<span style="color: #008b8b;">std</span>::string_view) { <span style="color: #a020f0;">return</span> JSON_Value&lt;Depth&gt;(<span style="color: #008b8b;">false</span>); },
             make_string_parser(<span style="color: #8b2252;">"false"</span><span style="color: #008b8b;">s</span>v))
      | fmap([] (<span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">n</span>) { <span style="color: #a020f0;">return</span> JSON_Value&lt;Depth&gt;(n); },
             number_parser())
      | fmap([] (<span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">str</span>) { <span style="color: #a020f0;">return</span> JSON_Value&lt;Depth&gt;(str); },
             string_parser())
      | array_parser&lt;Depth&gt;()
      | object_parser&lt;Depth&gt;();
    <span style="color: #a020f0;">return</span> skip_whitespace() &lt; p;
  }
  <span style="color: #0000ff;">...</span>
</pre>
</div>

<aside class="notes">
<p>
<code>value_parser</code> is the top level entry point to our parser.
</p>

<p>
Each argument of alternation must return the same type: in this case, they are
<code>JSON_Value</code> parsers, obtained from each other parse type by fmapping in an
appropriate function.
</p>

<p>
Note the way we eat whitespace before a value. Easy with the applicative
operator. It would be "easy" to sprinkle <code>skip_whitespace()</code> everywhere and it
would work&#x2026; but a more disciplined approach is to eating whitespace <b>before</b>
the parses that need it.
</p>

</aside>

</section>
<section id="slide-orge7d4088">
<h3 id="orge7d4088">Recursive parsing structure</h3>
<div class="org-src-container">

<pre  class="src src-c++">  <span style="color: #0000ff;">...</span>
  <span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span> = max_parse_depth&gt;
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> array_parser() { <span style="color: #0000ff;">...</span> }

  <span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span> = max_parse_depth&gt;
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">key_value_parser</span>() { <span style="color: #0000ff;">...</span> }

  <span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span> = max_parse_depth&gt;
  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">object_parser</span>() { <span style="color: #0000ff;">...</span> }
};

<span style="color: #a020f0;">template</span> &lt;&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #008b8b;">recur</span>::<span style="color: #0000ff;">value_parser</span>&lt;0&gt;() {
  <span style="color: #a020f0;">return</span> fail(<span style="color: #228b22;">JSON_Value</span>&lt;0&gt;{});
}

<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a020f0;">operator</span> <span style="color: #8b2252;">""</span> _json(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">char</span>* <span style="color: #a0522d;">str</span>, <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">len</span>) {
  <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">recur</span>::value_parser&lt;&gt;()(<span style="color: #008b8b;">std</span>::string_view{str, len});
}
</pre>
</div>

<aside class="notes">
<p>
The body of everything is too much code to show, but you can imagine how these
work.
</p>

<p>
For <code>array_parser</code>, we parse an open square bracket, then we use our
<code>separated_by</code> combinator to parse values separated by commas, then we parse a
closing square bracket. The JSON value we return is an array type value which
has had its array member accumulated with the comma-separated values we parsed.
</p>

<p>
Object parser is similar, but open/close curly braces, and key-value pairs
separated by commas. A key-value pair is itself a string followed by a colon
followed by a value.
</p>

<p>
Each time we recurse through <code>value_parser</code>, we decrement the <code>Depth</code>
template value to produce the next level of the JSON tree.
</p>

<p>
Note the use of <code>fail</code>: an easy way to provide the right type for the base case.
</p>

</aside>

</section>
</section>
<section>
<section id="slide-org1989218">
<h2 id="org1989218">Parsing JSON Value Literals (Better)</h2>
<p>
<br />
What we have so far is the simplest proof-of-concept.<br />
<br />
<br />
It works (for suitable values of "works").<br />
<br />
<br />
It's a good starting point, but there are a few problems we need to address.
</p>

<aside class="notes">
<p>
What we have so far is a good starting point. The parsing toolkit is pretty useful.
</p>

</aside>

</section>
<section id="slide-org38730cf">
<h3 id="org38730cf">Problem 1: A JSON number isn't an <code>int</code></h3>

<div class="figure">
<p><img src="./json_number.png" alt="json_number.png" />
</p>
</div>

<aside class="notes">
<p>
From json.org
</p>

<p>
A json number is considerably more complex to parse than an int.
</p>

<p>
But this can be done&#x2026;
</p>

<p>
You can see here we have some optional values in the parse. <code>option</code> is a useful
combinator to add for that. (Run a parser, and if it fails, return a default value.)
</p>

</aside>

</section>
<section id="slide-org48f3373">
<h3 id="org48f3373">Problem 2: A JSON string isn't a <code>string_view</code></h3>

<div class="figure">
<p><img src="./json_string.png" alt="json_string.png" />
</p>
</div>

<aside class="notes">
<p>
Strings are quite tricky to parse actually.
</p>

<p>
Non-unicode escaped characters aren't especially hard. We can use <code>operator&lt;</code> to
match and discard a slash, then convert the following character appropriately.
Unicode characters are a little more exacting.
</p>

<p>
The essential point here is that we can't get away with just outputting part of
the <code>string_view</code> that was the input. Parsing strings actually involves
transforming the input into a different, and differently-sized, output.
</p>

<p>
But again, we have all the tools to do this.
</p>

</aside>

</section>
<section id="slide-org982d3be">
<h3 id="org982d3be">Problem 3: Template instantiation</h3>
<div class="org-src-container">

<pre  class="src src-bash">$ time make
[ 50%] Building CXX object main.cpp.o
[100%] Linking CXX executable constexpr-all-the-things
[100%] Build target constexpr-all-the-things

real    A BLOODY...
user     LONG...
sys       TIME
$
</pre>
</div>

<aside class="notes">
<p>
We need to get rid of some templates.
</p>

</aside>

</section>
<section id="slide-org65732a3">
<h3 id="org65732a3">Problem 4: Arbitrary Limits</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">inline</span> <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">max_parse_depth</span>{3};

<span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">max_vector_size</span>{6};
<span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">max_map_size</span>{6};

<span style="color: #a020f0;">namespace</span> <span style="color: #008b8b;">cx</span>
{
  <span style="color: #a020f0;">using</span> <span style="color: #228b22;">string</span> = <span style="color: #228b22;">basic_string</span>&lt;<span style="color: #228b22;">char</span>, 32&gt;;
}
</pre>
</div>

<aside class="notes">
<p>
Nobody likes arbitrary limits. And these are some pretty small limits, at that.
</p>

</aside>

</section>
<section id="slide-orgae7d2f2">
<h3 id="orgae7d2f2">Getting Rid Of Template Slowness</h3>
<p>
All this recursive templatery is a problem.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">Depth</span>=5&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Data</span>
  {
    <span style="color: #0000ff;">...</span>
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">vector</span>&lt;<span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_vector_size&gt; array;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">map</span>&lt;<span style="color: #008b8b;">cx</span>::static_string, <span style="color: #228b22;">JSON_Value</span>&lt;Depth-1&gt;, max_map_size&gt; <span style="color: #a0522d;">object</span>;
  };
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>

</section>
<section id="slide-org10c82ad">
<h3 id="org10c82ad">Solution: More Parsing!</h3>
<p>
<br />
What we have is a parser for JSON values.<br />
<br />
But we could create more parsers&#x2026;<br />
<br />
</p>
<p class="fragment (appear)">
How about a parser for the <b>number</b> of JSON values required?
</p>

<aside class="notes">
<p>
Of course a parser can produce anything: it doesn't have to produce just JSON
values. If we could parse out the number of values required by a literal, we
could right-size an array of JSON values and then do another pass over the
literal with our actual value parser, outputting into the array.
</p>

</aside>

</section>
<section id="slide-orgbf9a71e">
<h3 id="orgbf9a71e">Number-of-values Parser</h3>
<p>
We can write a parser that computes the number of values in a literal:
</p>

<ul>
<li>Array ⇒ 1 + number of values in children</li>
<li>Object ⇒ 1 + number of values in children</li>
<li>Everything else ⇒ 1</li>

</ul>

<p>
We can reuse some structural components of our value parser, and a
number-of-values parser is simpler in many places.
</p>

</section>
<section id="slide-org1de3e06">
<h3 id="org1de3e06">Number-of-values Parser</h3>
<p>
Take the recursive function templates out of our value parser: instead, the
struct itself is a template containing the right-sized array of values.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">N</span>&gt;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">recur</span>
{
  <span style="color: #a020f0;">using</span> <span style="color: #228b22;">V</span> = <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">vector</span>&lt;JSON_Value, N&gt;;
  <span style="color: #228b22;">V</span> <span style="color: #a0522d;">vec</span>{};

  <span style="color: #a020f0;">constexpr</span> <span style="color: #0000ff;">recur</span>(<span style="color: #228b22;">parse_input_t</span> <span style="color: #a0522d;">s</span>) {
    value_parser(vec)(s);
  }

  <span style="color: #a020f0;">static</span> <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">value_parser</span>(<span style="color: #228b22;">V</span>&amp; <span style="color: #a0522d;">v</span>);
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>

<aside class="notes">
<p>
A major source of compilation slowness was instantiating the parser function
templates.
</p>

<p>
The parser functions now do much the same as before except they <code>push_back</code> the
parsed values into the array. And they <code>return</code> the array index of the element
they created.
</p>

<p>
We do the parsing on construction just to make things easy.
</p>

</aside>

</section>
<section id="slide-org31ca8bc">
<h3 id="org31ca8bc">Non-templated <code>JSON_Value</code></h3>
<p>
Now we can have a <code>JSON_Value</code> that isn't a template.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Data</span>
  {
    <span style="color: #0000ff;">...</span>
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">vector</span>&lt;<span style="color: #008b8b;">std</span>::size_t, max_vector_size&gt; array;
    <span style="color: #008b8b;">cx</span>::<span style="color: #228b22;">map</span>&lt;<span style="color: #008b8b;">cx</span>::static_string, <span style="color: #008b8b;">std</span>::size_t, max_map_size&gt; <span style="color: #a0522d;">object</span>;
  };
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>

<p>
The array and object values store offsets into the externalized array.
</p>

<aside class="notes">
<p>
Now that we have externalized the storage of the values, the arrays and objects
inside the <code>JSON_Value</code> store the offsets of their children.
</p>

<p>
I tried having them store pointers to JSON<sub>Values</sub>, but that didn't work
<code>constexpr</code>.
</p>

</aside>

</section>
<section id="slide-org13c4669">
<h3 id="org13c4669">Example parse</h3>
<p>
<br />
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = <span style="color: #8b2252;">"[1, [2, 3], 4]"</span>_json;
</pre>
</div>
<p>
<br />
Number of values: 6 (2 arrays, 4 numbers)<br />
<br />
<object type="image/svg+xml" data="./array_diagram.svg" class="org-svg">
Sorry, your browser does not support SVG.</object>
</p>

<aside class="notes">
<p>
Note the offset numbers for the array(s) here. They are not indices into the
external storage yet, they are just offsets from the current.
</p>

</aside>

</section>
<section id="slide-orgba73032">
<h3 id="orgba73032">Driving the Parse</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">template</span> &lt;<span style="color: #228b22;">char</span><span style="color: #0000ff;">...</span> <span style="color: #a0522d;">Cs</span>&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #0000ff;">numobjects</span>()
{
  <span style="color: #a020f0;">const</span> <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">initializer_list</span>&lt;<span style="color: #228b22;">char</span>&gt; <span style="color: #a0522d;">il</span>{Cs<span style="color: #0000ff;">...</span>};
  <span style="color: #a020f0;">return</span> <span style="color: #008b8b;">numobjects_recur</span>&lt;&gt;::value_parser()(
      <span style="color: #008b8b;">std</span>::string_view(il.begin(), il.size()))-&gt;first;
}

<span style="color: #a020f0;">template</span> &lt;<span style="color: #a020f0;">typename</span> <span style="color: #228b22;">T</span>, <span style="color: #228b22;">T</span><span style="color: #0000ff;">...</span> <span style="color: #a0522d;">Ts</span>&gt;
<span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a020f0;">operator</span> <span style="color: #8b2252;">""</span> _json()
{
  <span style="color: #a020f0;">const</span> <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">initializer_list</span>&lt;<span style="color: #228b22;">T</span>&gt; <span style="color: #a0522d;">il</span>{Ts<span style="color: #0000ff;">...</span>};
  <span style="color: #a020f0;">return</span> recur&lt;<span style="color: #228b22;">numobjects</span>&lt;Ts<span style="color: #0000ff;">...</span>&gt;()&gt;(
      <span style="color: #008b8b;">std</span>::string_view(il.begin(), il.size())).vec;
}
</pre>
</div>

<aside class="notes">
<p>
In order to get "constexpr arguments" we have to switch to the template version
of the literal operator (gnu extension based on N3599). That way we can pass the
template arguments on to our numobjects parser.
</p>

<p>
Note we're making a <code>string_view</code> out of the <code>initializer_list</code> expansion.
</p>

<p>
What's returned from the top-level parse is the vector of values. The "root"
value is at index 0.
</p>

</aside>

</section>
<section id="slide-org5bfac6c">
<h3 id="org5bfac6c">Problem 3: Solved</h3>
<p>
<br />
Cost: an extra pass<br />
<br />
Benefits:
</p>
<ul>
<li>quicker compilation (no recursive templates!)</li>
<li>no arbitrary hardcoded limit to depth</li>

</ul>
<p>
<br />
</p>
<div class="org-src-container">

<pre  class="fragment appear"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = <span style="color: #8b2252;">"([[[[[[[[[[[[1]]]]]]]]]]]])"</span>_json;
<span style="color: #a020f0;">static_assert</span>(jsval[0][0][0][0][0][0][0][0][0][0][0][0][0].to_Number() == 1);
</pre>
</div>

<aside class="notes">
<p>
The cost of the extra pass is much less than the cost of instantiating recursive
templates, especially since the number-of-values parser is much simpler than
the full parser.
</p>

<p>
And arbitrary depth is a significant win.
</p>

</aside>

</section>
<section id="slide-org7056bcb">
<h3 id="org7056bcb">Problem 4: Arbitrary limits</h3>
<p>
We still have limits on:
</p>

<ul>
<li>string size</li>
<li>array size</li>
<li>object (map) size</li>

</ul>

<p class="fragment appear">
Can we use the same strategy of precomputing size to combat these?
</p>

</section>
<section id="slide-org42695dd">
<h3 id="org42695dd">Removing string size restriction</h3>
<p>
We <b>can</b> use the same technique:
</p>
<ul>
<li class="fragment appear">precompute the total string size for the value</li>
<li class="fragment appear">rightsize a char buffer</li>
<li class="fragment appear">store <code>{offset, extent}</code> in the string <code>JSON_Value</code> as we parse</li>

</ul>
<p>
<br />
<br />
</p>
<p class="fragment appear">
We can do the number-of-values and total-string-size computation in a single
pass<br />
(that returns the pair of sizes).
</p>

<aside class="notes">
<p>
Structural bindings don't work <code>constexpr</code>.
</p>

</aside>

</section>
<section id="slide-org5585b3d">
<h3 id="org5585b3d">String size limit removed</h3>
<p>
<br />
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = R<span style="color: #000000; background-color: #ffffff;">"</span><span style="color: #8b2252;">(["X", ["ALL", "the"], "things!"])</span><span style="color: #000000; background-color: #ffffff;">"</span>_json;
</pre>
</div>
<p>
<br />
Number of values: 6 (2 arrays, 4 strings)<br />
Total string size: 14 (1 + 3 + 3 + 7)<br />
<br />
<object type="image/svg+xml" data="./string_size_diagram.svg" class="org-svg">
Sorry, your browser does not support SVG.</object>
</p>

</section>
<section id="slide-orgd8b9a57">
<h3 id="orgd8b9a57">Remaining limits</h3>
<p>
We still have limits on:
</p>

<ul>
<li>array size</li>
<li>object (map) size</li>

</ul>

<p>
We can't naively do the same thing we did with strings, because values within
arrays/objects aren't contiguous.
</p>

<aside class="notes">
<p>
We would like to be able to represent arrays as <code>{offset, extent}</code> but this is
only possible if the values contained within the array are stored contiguously.
</p>

</aside>

</section>
<section id="slide-orge73cda8">
<h3 id="orge73cda8">Arrays/Objects Aren't Contiguous</h3>
<p>
As we saw before, because of arbitrary nesting.
<br />
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = <span style="color: #8b2252;">"[1, [2, 3], 4]"</span>_json;
</pre>
</div>
<p>
<br />
<object type="image/svg+xml" data="./array_diagram.svg" class="org-svg">
Sorry, your browser does not support SVG.</object>
</p>

<aside class="notes">
<p>
This is because of the inherent depth-first traversal of parsing.
</p>

<p>
So how can we make the storage of the compound values contiguous?
</p>

</aside>

</section>
<section id="slide-orgca118e3">
<h3 id="orgca118e3">Add another pass</h3>
<p>
Add a pass to make the parser "breadth-first".
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">union</span> <span style="color: #228b22;">Data</span>
  {
    <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> <span style="color: #a0522d;">unparsed</span>;
    <span style="color: #228b22;">bool</span> <span style="color: #a0522d;">boolean</span>;
    <span style="color: #228b22;">double</span> <span style="color: #a0522d;">number</span>;
    <span style="color: #0000ff;">...</span>
  };
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>

<aside class="notes">
<p>
We're parsing a <code>string_view</code> that represents a JSON value. Every JSON value
contained is a <code>string_view</code> inside the top-level <code>string_view</code>.
</p>

<p>
All we need is a parser that returns the <code>string_view</code> for its value. We can
then use it to parse the children of the array value and store each as an
unparsed <code>string_view</code>. Contiguously!
</p>

<p>
What was earlier <code>struct</code> is <code>union</code> here.
</p>

</aside>

</section>
<section id="slide-orgadbb965">
<h3 id="orgadbb965">"Breadth-first" Parsing</h3>
<p>
Now the array is parsed contiguously.
<br />
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = <span style="color: #8b2252;">"[1, [2, 3], 4]"</span>_json;
</pre>
</div>
<p>
<br />
<object type="image/svg+xml" data="./breadth_first_diagram.svg" class="org-svg">
Sorry, your browser does not support SVG.</object>
</p>

<aside class="notes">
<p>
The diagram shows the intermediate stage of parsing the array. The array is
stored as offset + extent.
</p>

<p>
Once the array is parsed so that its immediate children occupy contiguous
storage, we go back and parse its children again into "real" JSON values that
are appended in the storage.
</p>

</aside>

</section>
<section id="slide-orgee9e4d3">
<h3 id="orgee9e4d3">As Arrays, so Objects</h3>
<p>
<br />
Arrays are now <code>{offset, extent}</code>, so there is no limit on array size.<br />
<br />
Objects could be arrays of (string, value).<br />
<br />
We just need to deal with object keys.
</p>

<aside class="notes">
<p>
There is one remaining limit: the size of an object key (because it's a string).
</p>

<p>
Well, now JSON values are small, and can store arbitrary length strings&#x2026; so we
might as well store an object key as a JSON value.
</p>

</aside>

</section>
<section id="slide-org5f047ff">
<h3 id="org5f047ff">Object storage</h3>
<p>
Objects are alternating strings and arbitrary values.
<br />
</p>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">jsval</span> = R<span style="color: #000000; background-color: #ffffff;">"</span><span style="color: #8b2252;">({"McKern":2,  "McGoohan":6})</span><span style="color: #000000; background-color: #ffffff;">"</span>_json;
</pre>
</div>
<p>
<br />
<object type="image/svg+xml" data="./object_diagram.svg" class="org-svg">
Sorry, your browser does not support SVG.</object>
</p>

<aside class="notes">
<p>
Of course, 6 here should really be NaN. Perhaps that's another talk :)
</p>

</aside>

</section>
<section id="slide-orgda1da0f">
<h3 id="orgda1da0f">Finally, no limits!</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">JSON_Value</span>
{
  <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">ExternalView</span> {
    <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">offset</span>;
    <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">extent</span>;
  };

  <span style="color: #a020f0;">union</span> <span style="color: #228b22;">Data</span> {
    <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">string_view</span> <span style="color: #a0522d;">unparsed</span>;
    <span style="color: #228b22;">bool</span> <span style="color: #a0522d;">boolean</span>;
    <span style="color: #228b22;">double</span> <span style="color: #a0522d;">number</span>;
    <span style="color: #228b22;">ExternalView</span> <span style="color: #a0522d;">external_string</span>;
    <span style="color: #228b22;">ExternalView</span> <span style="color: #a0522d;">external_array</span>;
    <span style="color: #228b22;">ExternalView</span> <span style="color: #a0522d;">external_object</span>;
  };
  <span style="color: #0000ff;">...</span>
};
</pre>
</div>

<aside class="notes">
<p>
This is the final representation of a JSON value as produced by our parsing
scheme.
</p>

</aside>

</section>
<section id="slide-orgc1309e0">
<h3 id="orgc1309e0">Parsing: Conclusion</h3>
<ul>
<li class="fragment appear"><code>constexpr</code> lambdas enable composable compile-time parsing</li>
<li class="fragment appear">parser combinators enable more complex literals</li>
<li class="fragment appear">multiple passes can be used thanks to template UDL operators and <code>string_view</code></li>
<li class="fragment appear">adding extra passes can solve almost any problem&#x2026;</li>
<li class="fragment appear">could parsing be helped by a (good?) C++ concept?</li>

</ul>

</section>
<section id="slide-org406f307">
<h3 id="org406f307">Demo?</h3>
<p>
Here's one I prepared earlier&#x2026;
</p>

</section>
</section>
<section>
<section id="slide-org13435fe">
<h2 id="org13435fe">The Future: Problems and Proposals</h2>
<aside class="notes">
<p>
Jason to talk through this section.
</p>

</aside>

</section>
<section id="slide-orgf8af64a">
<h3 id="orgf8af64a">The destructor problem</h3>
<p>
Currently any type with a non-trivial destructor cannot be used in <code>constexpr</code> context.
</p>

<p>
trivially destructible quiz time!
</p>

</section>
<section id="slide-org8c3d4fe">
<h3 id="org8c3d4fe"><code>is_trivially_destructible</code></h3>
<p>
Does this <code>static_assert</code> succeed?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">S</span> {
};

<span style="color: #a020f0;">static_assert</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">is_trivially_destructible_v</span>&lt;<span style="color: #228b22;">S</span>&gt;);
</pre>
</div>

</section>
<section id="slide-orgb29a117">
<h3 id="orgb29a117"><code>is_trivially_destructible</code></h3>
<p>
Does this <code>static_assert</code> succeed?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">S</span> {
  <span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span>;
};

<span style="color: #a020f0;">static_assert</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">is_trivially_destructible_v</span>&lt;<span style="color: #228b22;">S</span>&gt;);
</pre>
</div>

</section>
<section id="slide-orgc206a5c">
<h3 id="orgc206a5c"><code>is_trivially_destructible</code></h3>
<p>
Does this <code>static_assert</code> succeed?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">S</span> {
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">unique_ptr</span>&lt;<span style="color: #228b22;">int</span>&gt; <span style="color: #a0522d;">i</span>;
};

<span style="color: #a020f0;">static_assert</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">is_trivially_destructible_v</span>&lt;<span style="color: #228b22;">S</span>&gt;);
</pre>
</div>

</section>
<section id="slide-org71140d3">
<h3 id="org71140d3"><code>is_trivially_destructible</code></h3>
<p>
Does this <code>static_assert</code> succeed?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">S</span> {
  ~<span style="color: #0000ff;">S</span>() {}
};

<span style="color: #a020f0;">static_assert</span>(<span style="color: #008b8b;">std</span>::<span style="color: #228b22;">is_trivially_destructible_v</span>&lt;<span style="color: #228b22;">S</span>&gt;);
</pre>
</div>

<aside class="notes">
<p>
If we put "~S() = default;" then that <i>is</i> trivially destructible.
</p>

</aside>

</section>
<section id="slide-org94ca9d2">
<h3 id="org94ca9d2">Why is this a problem?</h3>
<p>
It's easy to build a <code>constexpr</code> enabled type that can grow at runtime,<br />
or fail to compile if it gets too big in <code>constexpr</code> context.
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Container</span> {
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">array</span>&lt;<span style="color: #228b22;">int</span>, 10&gt; <span style="color: #a0522d;">data</span>{};
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">size_t</span> <span style="color: #a0522d;">length</span> = 0;
  <span style="color: #228b22;">int</span> *<span style="color: #a0522d;">extra_data</span> = <span style="color: #008b8b;">nullptr</span>;
  <span style="color: #228b22;">void</span> <span style="color: #0000ff;">push_back</span>(<span style="color: #a020f0;">const</span> <span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span>) {
    <span style="color: #a020f0;">if</span> (length &gt;= data.size()) {
      <span style="color: #a020f0;">if</span> (!extra_data) {
        extra_data = <span style="color: #a020f0;">new</span> <span style="color: #228b22;">int</span>[100];
      }
      extra_data[(length++) - data.size()] = i;
    } <span style="color: #a020f0;">else</span> {
      data[length++] = i;
    }
  }
};
</pre>
</div>

</section>
<section id="slide-org571f9b5">
<h3 id="org571f9b5">Why is this a problem?</h3>
<p>
<b>But</b>: as soon as we add a destructor, the class is no longer usable in a <code>constexpr</code> context.
</p>

<p>
So we can build this type, but we are required to leak memory<br />
if it grows beyond the static size!
</p>

</section>
<section id="slide-orgfa70d59">
<h3 id="orgfa70d59">Solutions to the <code>constexpr</code> destructor problem</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Container</span> {
  ~<span style="color: #0000ff;">Container</span>() {
    <span style="color: #006400;">// </span><span style="color: #006400;">this proposal allows for an empty destructor to be allowed</span>
    <span style="color: #a020f0;">if</span> <span style="color: #a020f0;">constexpr</span>(something) {
      <span style="color: #006400;">// </span><span style="color: #006400;">do something</span>
    }
  }
};
</pre>
</div>

</section>
<section id="slide-org758756d">
<h3 id="org758756d">Solutions to the <code>constexpr</code> destructor problem</h3>
<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #a020f0;">struct</span> <span style="color: #228b22;">Container</span> {
  ~<span style="color: #0000ff;">Container</span>() {
    <span style="color: #006400;">// </span><span style="color: #006400;">but why not treat it like any other constexpr code?</span>
    <span style="color: #006400;">// </span><span style="color: #006400;">allow it as long as only constexpr allowed actions</span>
    <span style="color: #006400;">// </span><span style="color: #006400;">happen at compile time?</span>
    <span style="color: #a020f0;">if</span> (extra_data) {
      <span style="color: #a020f0;">delete</span> [] extra_data;
    }
  }
};
</pre>
</div>

</section>
<section id="slide-orgad97946">
<h3 id="orgad97946">The debugging problem</h3>
<p>
On which line does GCC report an error?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span class="linenr"> 1: </span><span style="color: #a020f0;">constexpr</span> <span style="color: #228b22;">int</span> <span style="color: #0000ff;">do_something</span>()
<span class="linenr"> 2: </span>{
<span class="linenr"> 3: </span>  <span style="color: #228b22;">int</span> <span style="color: #a0522d;">val</span>[1]{};
<span class="linenr"> 4: </span>  <span style="color: #a020f0;">return</span> val[1];
<span class="linenr"> 5: </span>}
<span class="linenr"> 6: </span>
<span class="linenr"> 7: </span><span style="color: #228b22;">int</span> <span style="color: #0000ff;">main</span>()
<span class="linenr"> 8: </span>{
<span class="linenr"> 9: </span>  <span style="color: #a020f0;">constexpr</span> <span style="color: #a020f0;">auto</span> <span style="color: #a0522d;">val</span> = do_something();
<span class="linenr">10: </span>}
</pre>
</div>

</section>
<section id="slide-orgee8629c">
<h3 id="orgee8629c">The debugging problem</h3>
<p>
Several times during debugging we had to take the code from compile time context 
to runtime context to allow for actual debugging.
</p>

<aside class="notes">
<p>
In building the data structure, switching to runtime context was useful.
</p>

<p>
In building up parsers, it was mostly simplify expressions and puzzle over the types.
</p>

</aside>

</section>
<section id="slide-org78abcea">
<h3 id="org78abcea">A <code>constexpr</code> operator</h3>
<p>
This proposal solves the problem of "how do I know when I'm in a <code>constexpr</code>
context".
</p>


<div class="figure">
<p><img src="./constexpr_operator.png" alt="constexpr_operator.png" />
</p>
</div>

</section>
<section id="slide-org522a045">
<h3 id="org522a045"><code>constexpr_trace</code></h3>
<p>
This proposal adds debugging capability at compile time.
</p>


<div class="figure">
<p><img src="./constexpr_trace.png" alt="constexpr_trace.png" />
</p>
</div>

<aside class="notes">
<p>
This would be useful for reporting parse errors on <code>constexpr</code> literals.
</p>

</aside>

</section>
<section id="slide-orge492490">
<h3 id="orge492490"><code>constexpr_vector</code></h3>
<p>
This other proposal from the same author allows for a special type of <code>constexpr_vector</code>
that is allowed to grow and shrink at compile time only, requiring compiler support.
</p>


<div class="figure">
<p><img src="./constexpr_vector.png" alt="constexpr_vector.png" />
</p>
</div>

</section>
<section id="slide-org09d53eb">
<h3 id="org09d53eb"><code>constexpr</code> allocator support</h3>
<p>
<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0639r0.html">Changing attack vector of the <code>constexpr_vector</code></a> (P0639)
</p>

<p>
Antony Polukhin &amp; Alexander Zaitsev
</p>

</section>
<section id="slide-org4529878">
<h3 id="org4529878">STL possibilities: algorithms</h3>
<p>
<br />
Weakened complexity guarantees on <code>stable_sort</code>, <code>inplace_merge</code>, <code>stable_partition</code>?
(They make use of temporary buffers to improve complexity.)<br />
<br />
Are there others that might need to have<br />
weakened complexity guarantees for compile time use?
</p>

<aside class="notes">
<p>
The temporary buffers aren't required for the algorithms to be correct, merely
to make them efficient.
</p>

</aside>

</section>
<section id="slide-orgd6b4893">
<h3 id="orgd6b4893">STL possibilities: iterators</h3>
<p>
If you have a <code>constexpr</code> container, you want the iterators to all be <code>constexpr</code>.
</p>

<p>
Many iterators could be <code>constexpr</code> and usable in a <code>constexpr</code> context<br />
if the operations on the corresponding containers are.
</p>

<p>
e.g. if you have <code>constexpr push_back</code> on your <code>constexpr vector</code> type,<br />
<code>back_insert_iterator</code> could easily be <code>constexpr</code>.
</p>

</section>
<section id="slide-orgf32f986">
<h3 id="orgf32f986">Things that could (should) be <code>constexpr</code></h3>
<ul>
<li class="fragment appear"><code>std::swap</code> &amp; <code>std::exchange</code></li>
<li class="fragment appear"><code>std::pair</code>'s (and <code>std::tuple</code>'s) <code>operator=</code></li>
<li class="fragment appear"><code>std::back_insert_iterator</code></li>
<li class="fragment appear"><code>std::array::fill</code></li>
<li class="fragment appear"><code>std::reference_wrapper</code></li>
<li class="fragment appear"><code>std::initializer_list</code></li>
<li class="fragment appear">structured bindings</li>
<li class="fragment appear">&#x2026; ALL the things!</li>

</ul>

</section>
<section id="slide-orgeb007ae">
<h3 id="orgeb007ae">Implementation issues</h3>
<p>
It is clear that standard library implementations need extensive <code>constexpr</code>
tests.
</p>

<ul>
<li><code>std::string_view</code>'s <code>operator=</code></li>
<li>also <code>remove_prefix</code>, <code>remove_suffix</code></li>
<li>iterator issues</li>

</ul>

</section>
</section>
<section>
<section id="slide-org682f225">
<h2 id="org682f225">The Cost</h2>
<div class="outline-text-2" id="text-org682f225">
</div></section>
<section id="slide-org24b7c11">
<h3 id="org24b7c11">Cognitive Cost</h3>
<ul>
<li class="fragment appear">Flat data structures are easy to reason about</li>
<li class="fragment appear"><code>constexpr</code> code forces you to consider what your code is doing and the lifetime of objects (in a good way).</li>
<li class="fragment appear">Tree-like data structures are difficult to reason about</li>
<li class="fragment appear">Selecting data structure sizes can be difficult</li>
<li class="fragment appear">Error messages from heavily composed lambdas are&#x2026; challenging to deal with</li>
<li class="fragment appear">Debugging often currently means "go back and think about the types"</li>

</ul>

<aside class="notes">
<p>
Is recursive computation harder to reason about? It depends on the problem, I think.
</p>

</aside>

</section>
<section id="slide-org3161e91">
<h3 id="org3161e91">Compile-time Cost - Debug Build</h3>
<ul>
<li class="fragment appear">6GB RAM!</li>
<li class="fragment appear">&gt;2 Minutes Build Time</li>
<li class="fragment appear">338K Binary</li>
<li class="fragment appear">Tweaking debug level can have a great effect. This might be related to symbol sizes.</li>

</ul>

<aside class="notes">
<p>
Explain exactly <b>what</b> is being built here?
</p>

<p>
Changing -g3 to -g1 greatly improves build time/space.
</p>

</aside>

</section>
<section id="slide-org5e9189f">
<h3 id="org5e9189f">Compile-time Cost - Release Build</h3>
<ul>
<li class="fragment appear">328MB RAM</li>
<li class="fragment appear">5s Build Time</li>
<li class="fragment appear">9K Binary</li>

</ul>

<aside class="notes">
<p>
This is pretty acceptable, especially when you consider that you are potentially
replacing whole steps in the build chain, possibly reducing the need to maintain
code generation tools, and moving the one source of truth into the C++ itself.
</p>

</aside>

</section>
<section id="slide-org9d91ed8">
<h3 id="org9d91ed8">Compile-time Cost - Comparison</h3>
<p>
Using the same nightly build of GCC, how long does this take to compile?
</p>

<div class="org-src-container">

<pre  class="src src-c++"><span style="color: #483d8b;">#include</span> <span style="color: #8b2252;">&lt;regex&gt;</span>

<span style="color: #228b22;">int</span> <span style="color: #0000ff;">main</span>()
{
  <span style="color: #008b8b;">std</span>::<span style="color: #228b22;">regex</span> <span style="color: #a0522d;">attribute</span>(R<span style="color: #000000; background-color: #ffffff;">"</span><span style="color: #8b2252;">(\s+(\S+)\s*=\s*('|")(.*?)\2)</span><span style="color: #000000; background-color: #ffffff;">"</span>);
}
</pre>
</div>

<p class="fragment (appear)">
5s Debug, 7.5s Release
</p>

<aside class="notes">
<p>
Slow build times are not unknown to the STL today.
</p>

</aside>

</section>
</section>
<section>
<section id="slide-org9b08a90">
<h2 id="org9b08a90">Conclusion</h2>
<ul>
<li class="fragment appear">All <del>but 3</del> standard algorithms can (easily?) be made <code>constexpr</code></li>
<li class="fragment appear">Standard libraries need <code>constexpr</code> testing to catch issues</li>
<li class="fragment appear">Many iterator operations could be made <code>constexpr</code> for use with <code>constexpr</code> containers</li>
<li class="fragment appear">Some interaction with C, e.g. <code>&lt;cmath&gt;</code> may hold back some operations</li>
<li class="fragment appear"><code>constexpr</code> lambdas unlock the potential for complex UDLs</li>
<li class="fragment appear"><code>constexpr</code> allocators and <code>constexpr</code> destructors would make it possible to unify <code>constexpr</code> containers with regular ones</li>

</ul>

<p class="fragment appear">
Thanks!<br/>
<a href="http://twitter.com/ben_deane">@ben_deane</a> <a href="http://twitter.com/lefticus">@lefticus</a> <br/>
<a href="https://github.com/lefticus/constexpr_all_the_things">https://github.com/lefticus/constexpr_all_the_things</a>
</p>
</section>
</section>
</div>
</div>
<script src="./reveal.js/lib/js/head.min.js"></script>
<script src="./reveal.js/js/reveal.js"></script>

<script>
// Full list of configuration options available here:
// https://github.com/hakimel/reveal.js#configuration
Reveal.initialize({

controls: true,
progress: true,
history: true,
center: true,
slideNumber: 'c/t',
rollingLinks: false,
keyboard: true,
overview: true,
width: 1600,
height: 900,
margin: 0.10,
minScale: 0.50,
maxScale: 2.50,

theme: Reveal.getQueryHash().theme, // available themes are in /css/theme
transition: Reveal.getQueryHash().transition || 'none', // default/cube/page/concave/zoom/linear/fade/none
transitionSpeed: 'default',
multiplex: {
    secret: '', // null if client
    id: '', // id, obtained from socket.io server
    url: '' // Location of socket.io server
},

// Optional libraries used to extend on reveal.js
dependencies: [
 { src: './reveal.js/lib/js/classList.js', condition: function() { return !document.body.classList; } },
 { src: './reveal.js/plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
 { src: './reveal.js/plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
 { src: './reveal.js/plugin/zoom-js/zoom.js', async: true, condition: function() { return !!document.body.classList; } },
 { src: './reveal.js/plugin/notes/notes.js', async: true, condition: function() { return !!document.body.classList; } }]
});
</script>
</body>
</html>
